{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Array Nesting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: arrayNesting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组嵌套"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>索引从<code>0</code>开始长度为<code>N</code>的数组<code>A</code>，包含<code>0</code>到<code>N - 1</code>的所有整数。找到最大的集合<code>S</code>并返回其大小，其中 <code>S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }</code>且遵守以下的规则。</p>\n",
    "\n",
    "<p>假设选择索引为<code>i</code>的元素<code>A[i]</code>为<code>S</code>的第一个元素，<code>S</code>的下一个元素应该是<code>A[A[i]]</code>，之后是<code>A[A[A[i]]]...</code> 以此类推，不断添加直到<code>S</code>出现重复的元素。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> A = [5,4,0,3,1,6,2]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> \n",
    "A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.\n",
    "\n",
    "其中一种最长的 S[K]:\n",
    "S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; nums.length</code></li>\n",
    "\t<li><code>A</code>中不含有重复的元素。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [array-nesting](https://leetcode.cn/problems/array-nesting/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [array-nesting](https://leetcode.cn/problems/array-nesting/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,0,3,1,6,2]', '[0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            count = 0\n",
    "            while nums[i] < l:\n",
    "                next = nums[i]\n",
    "                nums[i] = l\n",
    "                i = next\n",
    "                count += 1\n",
    "            ans = max(count,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        vis = [False] * n\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            while not vis[i]:\n",
    "                vis[i] = True\n",
    "                i = nums[i]\n",
    "                cnt += 1\n",
    "            ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        # 图\n",
    "        ans, n = 0, len(nums)\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            node = i\n",
    "            while not visited[node]:\n",
    "                visited[node] = True\n",
    "                node = nums[node]\n",
    "                cnt += 1\n",
    "            ans = max(ans, cnt)\n",
    "        return ans\n",
    "    def arrayNesting2(self, nums: List[int]) -> int:\n",
    "        def find(fa, x):\n",
    "            if fa[x] == x:\n",
    "                return x\n",
    "            return find(fa, fa[x])\n",
    "        fa = [x for x in range(len(nums))]\n",
    "        for x, y in enumerate(nums):\n",
    "            fa[find(fa, x)] = find(fa, y)\n",
    "        ans = Counter()\n",
    "        for x in fa:\n",
    "            ans[find(fa, x)] += 1\n",
    "        return max(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def arrayNesting(self, nums: List[int]) -> int:\n",
    "    #     num_to_idx = {n: i for i, n in enumerate(nums)}\n",
    "    #     dp = [-1] * len(nums)\n",
    "    #     for i, n in enumerate(nums):\n",
    "    #         if dp[i] != -1:\n",
    "    #             continue\n",
    "    #         dp[i] = 1\n",
    "    #         j = i\n",
    "    #         while num_to_idx[j] != i:\n",
    "    #             dp[num_to_idx[j]] = dp[j] + 1\n",
    "    #             j = num_to_idx[j]\n",
    "    #     return max(dp)\n",
    "\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ids = list(range(n))\n",
    "        size = [1] * n\n",
    "\n",
    "        def find_root(p: int) -> int:\n",
    "            while p != ids[p]:\n",
    "                p = ids[p]\n",
    "            return p\n",
    "\n",
    "        for i, j in enumerate(nums):\n",
    "            pi = find_root(i)\n",
    "            pj = find_root(j)\n",
    "            if pi == pj:\n",
    "                continue\n",
    "            if size[pi] < size[pj]:\n",
    "                ids[pi] = pj\n",
    "                size[pj] += size[pi]\n",
    "            else:\n",
    "                ids[pj] = pi\n",
    "                size[pi] += size[pj]\n",
    "\n",
    "        return max(size)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mp_all = []\n",
    "        i = l = 0\n",
    "        while l < n:\n",
    "            tar = set()\n",
    "            if mp_all:\n",
    "                judge = True\n",
    "                for x in mp_all:\n",
    "                    if nums[i] in x:\n",
    "                        judge = False\n",
    "                        break\n",
    "                if judge:\n",
    "                    while nums[i] not in tar:\n",
    "                        tar.add(nums[i])\n",
    "                        i = nums[i]\n",
    "                        if len(tar) == n:\n",
    "                            return n\n",
    "                    mp_all.append(tar)\n",
    "            else:\n",
    "                while nums[i] not in tar:\n",
    "                    tar.add(nums[i])\n",
    "                    i = nums[i]\n",
    "                    if len(tar) == n:\n",
    "                        return n\n",
    "                mp_all.append(tar)\n",
    "            l += 1\n",
    "            i = l\n",
    "        return len(max(mp_all, key=len))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        seen = set()\n",
    "        ans = 1\n",
    "        for index, num in enumerate(nums):\n",
    "            temp = 0\n",
    "            while nums[num] not in seen:\n",
    "                temp += 1\n",
    "                seen.add(nums[num])\n",
    "                num = nums[num]\n",
    "            ans = max(temp, ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            \n",
    "            idx = i\n",
    "            tmp = 0\n",
    "            while nums[idx] not in res:\n",
    "                tmp += 1\n",
    "                res.add(nums[idx])\n",
    "                idx = nums[idx]\n",
    "            ans = max(ans, tmp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dic={}\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            start=nums[i]\n",
    "            if start in dic:\n",
    "                continue\n",
    "            else:\n",
    "                res=1\n",
    "                tmp=nums[start]\n",
    "                while tmp!=start:\n",
    "                    if tmp in dic:\n",
    "                        res+=dic[tmp]\n",
    "                        dic[start]=res\n",
    "                        ans=max(ans,res)\n",
    "                        break\n",
    "                    else:\n",
    "                        dic[tmp]=-1\n",
    "                        res+=1\n",
    "                        tmp=nums[tmp]\n",
    "                ans=max(ans,res)\n",
    "                dic[start]=res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        Table = dict()\n",
    "        for i in range(len(nums)):\n",
    "            Table[i] = nums[i]\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if Table[i] == -1:\n",
    "                continue\n",
    "            templen=0\n",
    "            tempi = i\n",
    "            while Table[tempi] != -1:\n",
    "                t = tempi\n",
    "                tempi = Table[tempi]\n",
    "                Table[t] = -1\n",
    "                templen += 1\n",
    "            ans = max(ans,templen)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "\n",
    "        res = 0\n",
    "        prev = nums[0]\n",
    "        visitedEven = set()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in visitedEven:\n",
    "                visited = set()\n",
    "                cur = nums[i]\n",
    "\n",
    "                while cur not in visited:\n",
    "                    visitedEven.add(cur)\n",
    "                    visited.add(cur)\n",
    "                    cur = nums[cur]\n",
    "\n",
    "                res = max(res, len(visited))\n",
    "    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        vec = {}\n",
    "        tmax = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            vec[i] = v\n",
    "        for i in vec:\n",
    "            size = 0\n",
    "            s = set()\n",
    "            next = i\n",
    "            while next is not None:\n",
    "                s.add(next)\n",
    "                if len(s) > size:\n",
    "                    size += 1\n",
    "                    pnext = vec.get(next)\n",
    "                    vec[next]=None\n",
    "                    next=pnext\n",
    "                else:\n",
    "                    break\n",
    "            tmax = max(tmax, size)\n",
    "        return tmax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        tag = {}\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            tmp = i\n",
    "            if tmp not in tag:\n",
    "                cur = [tmp]\n",
    "                flag = set()\n",
    "                flag.add(tmp)\n",
    "                step = 1\n",
    "                while nums[tmp] not in flag:\n",
    "                    tmp = nums[tmp]\n",
    "                    cur.append(tmp)\n",
    "                    flag.add(tmp)\n",
    "                    if tmp in tag:\n",
    "                        step += tag[tmp]\n",
    "                        break\n",
    "                    step += 1\n",
    "                for j in cur:\n",
    "                    tag[j] = step\n",
    "                    ans = max(ans, step)\n",
    "                    step -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        dic = {}\n",
    "\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] in dic:\n",
    "                continue\n",
    "            temp = set()\n",
    "            val = nums[i]\n",
    "            while val not in temp:\n",
    "                dic[val] = 1\n",
    "                temp.add(val)\n",
    "                val = nums[val]\n",
    "            res = max(res, len(temp))\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        Table = dict()\n",
    "        for i in range(len(nums)):\n",
    "            Table[i] = [nums[i],0]\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if Table[i][1] != 0:\n",
    "                continue\n",
    "            templen=0\n",
    "            tempi = i\n",
    "            while Table[tempi][1] != i:\n",
    "                Table[tempi][1] = i\n",
    "                templen += 1\n",
    "                tempi = Table[tempi][0]\n",
    "            ans = max(ans,templen)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = collections.defaultdict(list)\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            arr = s[i]\n",
    "            j = i\n",
    "            while True:\n",
    "                if nums[j] not in visited:\n",
    "                    arr.append(nums[j])\n",
    "                    visited.add(nums[j])\n",
    "                    nums[j] = nums[nums[j]]\n",
    "                else:\n",
    "                    break\n",
    "        maxV = 0\n",
    "        for i in range(n):\n",
    "            maxV = max(maxV,len(s[i]))\n",
    "        return maxV\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        edge = {}\n",
    "        tmp_ans = {}\n",
    "        for i,x in enumerate(nums):\n",
    "            edge[i] = x\n",
    "            tmp_ans[i] = 0\n",
    "        vis = set()\n",
    "        for a,b in enumerate(nums):\n",
    "            if a not in vis:\n",
    "                stack = []\n",
    "                while a not in vis:\n",
    "                    vis.add(a)\n",
    "                    a = edge[a]\n",
    "                    stack.append(a)\n",
    "                last = a\n",
    "                while stack:\n",
    "                    tmp_ans[stack[-1]] = tmp_ans[last]+1\n",
    "                    last = stack.pop()\n",
    "        return max(tmp_ans.values())\n",
    "                \n",
    "                    \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        d = {i:x for i,x in enumerate(nums)}\n",
    "        s = set()\n",
    "        d2 = {}\n",
    "        while d!={}:\n",
    "            s1 = set(d)\n",
    "            d1 = d.copy()\n",
    "            if d1==d2:\n",
    "                break\n",
    "            d2 = d.copy()\n",
    "            for i in d:\n",
    "                t = 1\n",
    "                w = i\n",
    "                while w in s1 and d[w] in s1 and w!=d[w]:\n",
    "                    s1.remove(w)\n",
    "                    t+=1\n",
    "                    w = d[w]\n",
    "                s.add(t)\n",
    "            d = {i:d[i] for i in s1}\n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        ts = [-1] * n\n",
    "        dp = [0] * n\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            if ts[i] != -1: continue\n",
    "            t0 = ts[i] = t\n",
    "            t += 1\n",
    "            j = a[i]\n",
    "            while ts[j] == -1:\n",
    "                ts[j] = t\n",
    "                t += 1\n",
    "                j = a[j]\n",
    "            if ts[j] >= t0:\n",
    "                m = t - ts[j]\n",
    "                for _ in range(m):\n",
    "                    dp[j] = m\n",
    "                    j = a[j]\n",
    "        def dfs(i):\n",
    "            if dp[i] == 0: dp[i] = dfs(a[i]) + 1\n",
    "            return dp[i]\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        j_dic=collections.OrderedDict()\n",
    "        for i in range(len(nums)):\n",
    "            if str(i) in j_dic:\n",
    "                continue\n",
    "            dic=collections.OrderedDict()\n",
    "            dic[str(i)]=nums[i]\n",
    "            count=1\n",
    "            j=nums[i]\n",
    "            while str(j) not in dic:\n",
    "                j_dic[str(j)]=1\n",
    "                dic[str(j)]=nums[j]\n",
    "                count+=1\n",
    "                j=nums[j]\n",
    "            res=max(res,count)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "\n",
    "        def findRoot(x):\n",
    "            p = parent.get(x, x)\n",
    "            if p != x:\n",
    "                parent[x] = findRoot(p)\n",
    "            \n",
    "            return parent.get(x, x)\n",
    "        \n",
    "        def union(x, y):\n",
    "            px, py = findRoot(x), findRoot(y)\n",
    "            if px != py:\n",
    "                sizex, sizey = size.get(px, 1), size.get(py, 1)\n",
    "                if sizex < sizey:\n",
    "                    px, py = py, px\n",
    "\n",
    "                parent[py] = px\n",
    "                size[px] = sizex + sizey\n",
    "                return size[px]\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        parent = {}\n",
    "        size = {}\n",
    "        result = 1\n",
    "        for i in range(len(nums)):\n",
    "            result = max(result, union(i, nums[i]))\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        def findF(i):\n",
    "            fi = fs[i]\n",
    "            if fs[fi] != fi:\n",
    "                fs[i] = findF(fs[fi])\n",
    "            return fs[i]\n",
    "\n",
    "        def union(i, j):\n",
    "            fs[findF(i)] = findF(j)\n",
    "            return\n",
    "            '''\n",
    "            fi, fj = findF(i), findF(j)\n",
    "            if fi < fj:\n",
    "                fs[fj] = fi\n",
    "            elif fj < fi:\n",
    "                fs[fi] = fj\n",
    "            return\n",
    "            '''\n",
    "\n",
    "        n = len(nums)\n",
    "        fs = [i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            union(i, nums[i])\n",
    "        for i in range(n):\n",
    "            findF(i)\n",
    "        return max(Counter(fs).values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        self.visited = [0] * len(nums)\n",
    "        self.ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if self.visited[nums[i]] == 0:\n",
    "                self.dfs(nums, nums[i], 0)\n",
    "\n",
    "                cur_num, cur_len = nums[i], 0\n",
    "                while self.visited[cur_num] == 0:\n",
    "                    cur_len += 1\n",
    "                    self.visited[cur_num] = 1\n",
    "                    cur_num = nums[cur_num]\n",
    "                self.ans = max(self.ans, cur_len)\n",
    "\n",
    "        return self.ans\n",
    "    \n",
    "    def dfs(self, nums, cur_num, cur_length):\n",
    "        if self.visited[cur_num] == 1:\n",
    "            self.ans = max(self.ans, cur_length)\n",
    "            return\n",
    "\n",
    "        self.visited[cur_num] = 1\n",
    "        self.dfs(nums, nums[cur_num], cur_length + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        visited = set()\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            if x not in visited:\n",
    "                visited.add(x)\n",
    "                res = max(res, self.dfs(nums, x, visited) + 1)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, nums, x, visited):\n",
    "        if nums[x] not in visited:\n",
    "            visited.add(nums[x])\n",
    "            return self.dfs(nums, nums[x], visited) + 1\n",
    "        else:\n",
    "            return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    global lencur\n",
    "    lencur = 0\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        maxlen = 0\n",
    "        \n",
    "        def nextnum(i,nums):\n",
    "            global lencur\n",
    "            if nums[i] != -1:\n",
    "                nextn = nums[i]\n",
    "                nums[i] = -1\n",
    "                i = nextn\n",
    "                lencur += 1\n",
    "                nextnum(i,nums)\n",
    "                # print(lencur)\n",
    "\n",
    "        for i in nums:\n",
    "            global lencur\n",
    "            lencur = 0\n",
    "            nextnum(i,nums)\n",
    "            maxlen = max(maxlen, lencur)\n",
    "        return maxlen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "    \n",
    "    def find(self, node):\n",
    "        if self.parent[node] == node:\n",
    "            return node\n",
    "        self.parent[node] = self.find(self.parent[node])\n",
    "        return self.parent[node]\n",
    "    \n",
    "    def merge(self, node1, node2):\n",
    "        p1 = self.find(node1)\n",
    "        p2 = self.find(node2)\n",
    "        if p1 != p2:\n",
    "            self.parent[p1] = p2\n",
    "     \n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        union = UnionSet(len(nums))\n",
    "        for index, val in enumerate(nums):\n",
    "            union.merge(index, val)\n",
    "        for index, val in enumerate(nums):\n",
    "            p = union.find(val)\n",
    "            union.parent[index] = p\n",
    "        c = Counter(union.parent)\n",
    "        return max(c.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        record = [0] *len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            tmp = self.search(nums, record, i)\n",
    "            result = max(result, tmp)\n",
    "        return result\n",
    "\n",
    "    def search(self, nums, record,  i):\n",
    "        if record[i]!=0:\n",
    "            if record[i]==-1:\n",
    "                record[i] = 0\n",
    "        else:\n",
    "            record[i] = -1\n",
    "            record[i] = self.search(nums, record, nums[i]) + 1\n",
    "        return record[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        answer = 1\n",
    "        nums_length = len(nums)\n",
    "        for index in range(nums_length):\n",
    "            if nums[index] != 10 ** 5:\n",
    "                temp = nums[index]\n",
    "                nums[index] = 10 ** 5\n",
    "                answer = max(answer, searchLoop(nums, temp))\n",
    "        return answer\n",
    "\n",
    "def searchLoop(nums, index):\n",
    "    if nums[index] != 10 ** 5:\n",
    "        temp = nums[index]\n",
    "        nums[index] = 10 ** 5\n",
    "        return searchLoop(nums, temp) + 1\n",
    "    else:\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        def dfs(i):\n",
    "            if nums[i] == -1:\n",
    "                return 0\n",
    "            nxt, nums[i] = nums[i], -1\n",
    "            return 1 + dfs(nxt)\n",
    "\n",
    "        n = len(nums)\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "  def arrayNesting(self, nums: List[int]) -> int:\n",
    "    n = len(nums)\n",
    "    def f(i):\n",
    "      if nums[i] == -1: return 0\n",
    "      j = nums[i]\n",
    "      nums[i] = -1\n",
    "      return f(j) + 1\n",
    "    ans = 1\n",
    "    for x in nums:\n",
    "      if x == -1: continue\n",
    "      ans = max(ans, f(x))\n",
    "    return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        def dfs(idx):\n",
    "            if nums[idx] == -1:\n",
    "                return 0\n",
    "            nxt, nums[idx] = nums[idx], -1\n",
    "            return 1 + dfs(nxt)\n",
    "        return max([dfs(i) for i in range(len(nums))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def find(u):\n",
    "            if root[u] != u:\n",
    "                root[u] = find(root[u])\n",
    "            return root[u]\n",
    "        \n",
    "        def union(u, v):\n",
    "            ur, vr = find(u), find(v)\n",
    "            if ur != vr:\n",
    "                root[ur] = vr\n",
    "        \n",
    "        n = len(nums)\n",
    "        root = [i for i in range(n)]\n",
    "        for i, j in enumerate(nums):\n",
    "            if i != j:\n",
    "                union(i, j)\n",
    "        f = {}\n",
    "        for i in range(n):\n",
    "            r = find(i)\n",
    "            f[r] = f.get(r, 0) + 1\n",
    "        return max(f.values())\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        ans = -1\n",
    "        visit =  [False] * len(nums)\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            if visit[nums[i]]:\n",
    "                continue\n",
    "            visit[nums[i]] = True\n",
    "            count = 1\n",
    "            d = self.dfs(nums, nums[i], count, visit)\n",
    "            ans = max(ans, d)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, nums: List[int], v: int, cnt: int, vis: List[bool]) -> int:\n",
    "        value = nums[v]\n",
    "        \n",
    "        if vis[value]:\n",
    "            return cnt\n",
    "        \n",
    "        cnt += 1\n",
    "        vis[value] = True\n",
    "        return self.dfs(nums, value, cnt, vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, dp: List[int], nums: List[int], idx: int, select: dict):\n",
    "        if dp[idx] != -1:\n",
    "            return dp[idx]\n",
    "\n",
    "        if idx in select.keys():\n",
    "            return 0\n",
    "\n",
    "        select[idx] = 1\n",
    "        dp[idx] = self.dfs(dp, nums, nums[idx], select) + 1\n",
    "\n",
    "        return dp[idx]\n",
    "\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        dp = [-1] * nums.__len__()\n",
    "\n",
    "        for i in range(nums.__len__()):\n",
    "            if dp[nums[i]] == -1:\n",
    "                self.dfs(dp, nums, nums[i], {})\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        d={}\n",
    "        def find(x):\n",
    "            d[x]=d.get(x,x)\n",
    "            if x!=d[x]:\n",
    "                d[x]=find(d[x])\n",
    "            return d[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            d[find(x)]=find(y)\n",
    "        \n",
    "        def get_part():\n",
    "            map=defaultdict(int)\n",
    "            for i in range(len(nums)):\n",
    "                map[find(i)]+=1\n",
    "            return max(map.values())\n",
    "        for k,v in enumerate(nums):\n",
    "            union(k,v)\n",
    "        return get_part()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        visited = [0] * n\n",
    "        graph = {i:x for i ,x in enumerate(nums)}\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if visited[i] == 0:\n",
    "               count = max(count,self.dfs(graph,visited,i))\n",
    "        return count       \n",
    "\n",
    "\n",
    "    def dfs(self,graph,visited,i):\n",
    "        visited[i] = 1\n",
    "        count = 1\n",
    "        if visited[graph[i]] == 0:\n",
    "                count += self.dfs(graph,visited,graph[i])          \n",
    "        return  count         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        cache = {}\n",
    "\n",
    "        def dfs(index, path):\n",
    "            if index in cache:\n",
    "                return cache[index]\n",
    "            if nums[index] in path:\n",
    "                return path\n",
    "            path.add(nums[index])\n",
    "            cache[index] = dfs(nums[index], path)\n",
    "            return set()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            path = set()\n",
    "            s = dfs(i, path)\n",
    "\n",
    "\n",
    "        max_val = 0\n",
    "        for s in cache.values():\n",
    "            max_val = max(max_val, len(s))\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        cache = {}\n",
    "\n",
    "        def dfs(index, path):\n",
    "            if index in cache:\n",
    "                return cache[index]\n",
    "            if nums[index] in path:\n",
    "                return path\n",
    "            path.add(nums[index])\n",
    "            cache[index] = dfs(nums[index], path)\n",
    "            return set()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            path = set()\n",
    "            s = dfs(i, path)\n",
    "\n",
    "\n",
    "        max_val = 0\n",
    "        for s in cache.values():\n",
    "            max_val = max(max_val, len(s))\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs(start, visited):\n",
    "            nonlocal cnt\n",
    "            if not visited[start]:\n",
    "                visited[start] = True\n",
    "                cnt += 1\n",
    "                dfs(nums[start], visited)\n",
    "\n",
    "        res = 0\n",
    "        visited = [False] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            cnt = 1\n",
    "            visited[i] = True\n",
    "            dfs(num, visited)\n",
    "            res = max(res, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        flag=[0 for _ in nums]\n",
    "        ans=-1\n",
    "        def dfs(i:int,visit:List[int])->int:\n",
    "            if visit[i]:\n",
    "                return 0\n",
    "            visit[i]=1\n",
    "            return 1+dfs(nums[i],visit)\n",
    "        for index,n in enumerate(nums):\n",
    "            if flag[index]==0:\n",
    "                ans=max(ans,dfs(index,flag))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        flag = [-1] * n\n",
    "        def dfs(i):\n",
    "            if flag[i] != -1: return 0\n",
    "            flag[i] = 0\n",
    "            return dfs(nums[i]) + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if flag[i] == -1:\n",
    "                a = dfs(i)\n",
    "                if a > ans:\n",
    "                    ans = a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\n",
    "        def findnext(lst, current, now):\n",
    "            lst[now] = False\n",
    "            if not lst[nums[now]]:\n",
    "                return current\n",
    "            else:\n",
    "                return findnext(lst, current + 1, nums[now])\n",
    "        Max = 0\n",
    "        lst = [True for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if lst[i]:\n",
    "                result = findnext(lst, 1, i)\n",
    "                Max = max(Max, result)\n",
    "        return Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def arrayNesting(self, nums: List[int]) -> int:\r\n",
    "        def dfs(i):\r\n",
    "            if visited[i]:\r\n",
    "                return 0\r\n",
    "            visited[i] = True\r\n",
    "            return dfs(nums[i]) + 1\r\n",
    "        n = len(nums)\r\n",
    "        visited = [False] * n\r\n",
    "        res = 0\r\n",
    "        for i in range(n):\r\n",
    "            res = max(res, dfs(i))\r\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
